package com.itheima.com.排序;

public class 二分查找 {
    public static void main(String[] args) {
        int[] arr = {1, 5, 15, 17, 19, 20, 33, 43, 67, 99};
        int target = 19;
        int index = searchBinary(arr, target);
        System.out.println(index);
    }

    private static int searchBinary(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;
        int mid;
        while (l < r) {
            // int有最大值  会出现溢出
            // mid = (l + r) / 2;      // 解决方法   ==> l+(r-l)/2
            mid = (l + r) >>> 1; // 无符号右移1 效率高
            if (target == arr[mid]) {
                return mid;
            } else if (target < arr[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    private static int binarySearch(int[] a, int fromIndex, int toIndex,
                                    int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }
}
